Encryption is a common way to secure data, whether the data is sent over a non-secure network such as the Internet, or is stored remotely where security breaches might occur. Many encryption systems and standards are known. While such existing encryption systems are effective, such systems are not always efficient.
Cloud-based storage has become popular today. Rather than store documents and files locally, such as on personal computers or servers at a company premesis, the documents and files are stored or backed up at a remote location. When a user wishes to update a document, the user fetches the document from the remote storage, makes the updates, and sends the updated document back to the remote storage location.
The remote storage is typically accessed through the Internet. For security, the documents and files may be stored in an encrypted format at the remote storage location. The remote storage sends an encrypted document to the user, who then decrypts the document, makes the updates, and re-encrypts the document. The re-encrypted document is then sent over the Internet to the remote storage.
FIG. 1 highlights that prior-art encryption of a small change in clear text usually results in a large change in the encrypted cipher text. Sometimes only a small portion of encrypted data is changed, such as when a user updates a single sentence in a large document that is stored remotely.
FIG. 1 shows that the user made a small change in the unencrypted plain text or clear text, such as by changing the first letter from a lower-case “a” to a capital “A”. The rest of the document is unchanged.
In a traditional encryption system, once the updates are made and saved by the user, the entire document is encrypted again and new encrypted cipher text is generated. The new cipher text is typically completely different from the original cipher text. For example, the original clear text is encrypted to the string “UuEOKHa8yp” while the updated cipher text is encrypted to the string “cMWceJsjgo6”.
While such a complete change in cipher text is secure, it typically requires that the new cipher text for the whole document be re-transmitted to the remote storage location. Thus a small change in a document requires that a large amount of encrypted data be transmitted over limited-bandwidth networks.
What is desired is an encryption system that more efficiently updates encrypted cipher text. A re-encryption system is desired that changes only a portion of the cipher text, allowing a partial update of cipher text to be transmitted over networks for remote storage. A re-encryption system is desired that locates a segment of changed text within a sequence of encrypted blocks, and then re-encrypts only that changed segment. An encryption system that uses fixed-size cipher blocks and variable-sized segments is desired.